//
// Created by 123 on 2024/3/20.
//
#include <iostream>
#include <queue>

using namespace std;


//顶点对应数据类型
typedef int VertexType;
//边对应数据类型
typedef int EdgeType;

//图中最大点数为100个
#define MaxVertexNum 100

//弧顶
typedef struct ArcNode {
    int adjvex;//弧所指向的顶点的位置
    ArcNode *nextarc;//指向下一条的弧的指针
} ArcNode;

//边集
typedef struct VNode {
    VertexType data;//顶点数据
    ArcNode *firstarc;//指向第一条依附于该顶点的弧的指针
} VNode, AdjList[MaxVertexNum];
//图
typedef struct {
    AdjList vertices;//邻接表
    int vexnum, arcnum;//图的顶点数和弧数
} ALGraph;//ALGraph是以邻接表存储的图类型

//初始化图
ALGraph *initGraph(int vexnum, int arcnum);

//初始化边，其实就是弧顶
ArcNode *initArcNode(int adjvex);

//    1  {0, 1, 0, 0, 1, 0, 0, 0},
//    2  {1, 0, 0, 0, 0, 1, 0, 0},
//    3  {0, 0, 0, 1, 0, 1, 1, 0},
//    4  {0, 0, 1, 0, 0, 0, 1, 1},
//    5  {1, 0, 0, 0, 0, 0, 0, 0},
//    6  {0, 1, 1, 0, 0, 0, 1, 0},
//    7  {0, 0, 1, 1, 0, 1, 0, 1},
//    8  {0, 0, 0, 1, 0, 0, 1, 0},


bool isVisited[8] = {false, false, false, false, false, false, false, false,};
int d[8] = {9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999};


void bfs(ALGraph *graph, int vex) {
    cout << graph->vertices[vex - 1].data << "    ";

//    初始到自己距离为 1
    d[vex - 1] = 0;


    isVisited[vex - 1] = true;
    queue<int> que;
//    存放位置
    que.push(vex - 1);
    while (!que.empty()) {
        int v = que.front();
        que.pop();
        ArcNode *arcNode = graph->vertices[v].firstarc;
        while (arcNode != NULL) {
            if (!isVisited[arcNode->adjvex]) {

                //求最短路径 参考树的层序遍历，每一层在上一层的基础上加一
                d[arcNode->adjvex] = d[v] + 1;

                cout << graph->vertices[arcNode->adjvex].data << "    ";
                isVisited[arcNode->adjvex] = true;
                que.push(arcNode->adjvex);
            }
            arcNode = arcNode->nextarc;

        }
    }
    cout << endl;
}

int main() {
    ALGraph *graph = initGraph(8, 9);
    bfs(graph, 2);

    cout<<"-----------------------------------------"<<endl;
    cout<<" 2到各个节点的距离"<<endl;
    for (int i = 0; i < 8; ++i) {
        cout << graph->vertices[i].data << ": " << d[i] << "    ";
    } 
}

//初始化图
ALGraph *initGraph(int vexnum, int arcnum) {
    ALGraph *graph = (ALGraph *) malloc(sizeof(ALGraph));
    graph->vexnum = vexnum;
    graph->arcnum = arcnum;
//    初始化边集
    for (int i = 0; i < MaxVertexNum; ++i) {
        graph->vertices[i].firstarc = NULL;
        graph->vertices[i].data = 99999;//表示空值
    }
    //    加入点
    graph->vertices[0].data = 1;
    graph->vertices[1].data = 2;
    graph->vertices[2].data = 3;
    graph->vertices[3].data = 4;
    graph->vertices[4].data = 5;
    graph->vertices[5].data = 6;
    graph->vertices[6].data = 7;
    graph->vertices[7].data = 8;

//  1作弧尾
    ArcNode *n12 = initArcNode(2 - 1);
    ArcNode *n15 = initArcNode(5 - 1);
    n12->nextarc = n15;
    graph->vertices[0].firstarc = n12;

//  2作弧尾
    ArcNode *n21 = initArcNode(1 - 1);
    ArcNode *n26 = initArcNode(6 - 1);
    n21->nextarc = n26;
    graph->vertices[1].firstarc = n21;

//  3作弧尾
    ArcNode *n34 = initArcNode(4 - 1);
    ArcNode *n36 = initArcNode(6 - 1);
    ArcNode *n37 = initArcNode(7 - 1);
    n34->nextarc = n36;
    n36->nextarc = n37;
    graph->vertices[2].firstarc = n34;

//  4作弧尾
    ArcNode *n43 = initArcNode(3 - 1);
    ArcNode *n47 = initArcNode(7 - 1);
    ArcNode *n48 = initArcNode(8 - 1);
    n43->nextarc = n47;
    n47->nextarc = n48;
    graph->vertices[3].firstarc = n43;

//  5作弧尾
    ArcNode *n51 = initArcNode(1 - 1);
    graph->vertices[4].firstarc = n51;

//  6作弧尾
    ArcNode *n62 = initArcNode(2 - 1);
    ArcNode *n63 = initArcNode(3 - 1);
    ArcNode *n67 = initArcNode(7 - 1);
    n62->nextarc = n63;
    n63->nextarc = n67;
    graph->vertices[5].firstarc = n62;

//  7作弧尾
    ArcNode *n73 = initArcNode(3 - 1);
    ArcNode *n74 = initArcNode(4 - 1);
    ArcNode *n76 = initArcNode(6 - 1);
    ArcNode *n78 = initArcNode(8 - 1);
    n73->nextarc = n74;
    n74->nextarc = n76;
    n76->nextarc = n78;
    graph->vertices[6].firstarc = n73;

//  8作弧尾
    ArcNode *n84 = initArcNode(4 - 1);
    ArcNode *n87 = initArcNode(7 - 1);
    n84->nextarc = n87;
    graph->vertices[7].firstarc = n84;

    return graph;
}

//初始化边，其实就是弧顶
ArcNode *initArcNode(int adjvex) {
    ArcNode *node = (ArcNode *) malloc(sizeof(ArcNode));
    node->adjvex = adjvex;
    node->nextarc = NULL;
    return node;
}